package com.lisp.algorithm.c1e415;

public class MaxSubArray2 {

    /*
    f(a[], start, end) = f(a[], start, middle)
                       = f(a[], middle, end)
                       = f-containsMiddle(a[], middle, start, end)
    */
                       
    public static void main(String[] args) {
        int a[] = {-1, -2, -1};
        System.out.println(maxSubArray(a, 0, a.length));
    }
    
    private static SubArray maxSubArray(int a[], int start, int end) {
        if(start == end - 1) {
            return new SubArray(start, end, a[start]);
        } else {
            int middle = (start + end) / 2;
            SubArray left = maxSubArray(a, start, middle);
            SubArray right = maxSubArray(a, middle, end);
            SubArray containsMiddle = maxSubArrayContainsMiddle(a, middle, start, end);
            if(left.sum >= right.sum && left.sum >= containsMiddle.sum) {
                return left;
            } else if(right.sum >= left.sum && right.sum >= containsMiddle.sum) {
                return right;
            } else {
                return containsMiddle;
            }
        }
    }
    
    private static SubArray maxSubArrayContainsMiddle(int a[], int middle, int start, int end) {
        int leftMaxSum = Integer.MIN_VALUE;
        int leftSum = 0;
        int leftStart = middle;
        for(int i=middle; i>=start; i--) {
            leftSum = leftSum + a[i];
            if(leftSum > leftMaxSum) {
                leftMaxSum = leftSum;
                leftStart = i;
            }
        }
        
        int rightMaxSum = Integer.MIN_VALUE;
        int rightSum = 0;
        int rightEnd = middle+1;
        for(int j=middle+1; j<end; j++) {
            rightSum = rightSum + a[j];
            if(rightSum > rightMaxSum) {
                rightMaxSum = rightSum;
                rightEnd = j+1;
            }
        }
        
        return new SubArray(leftStart, rightEnd, leftMaxSum + rightMaxSum);
    }
}
